﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _5.BinarySearchTree.BinarySearchTree
{
    public class BinaryTree<T> : IEnumerable<T>
    {
        public BinaryNode<T> Root
        {
            get;
            private set;
        }

        public readonly Comparison<T> Comparison;
        
        public BinaryTree(Comparison<T> comparison)
        {
            this.Comparison = comparison;
        }

        public void Add(T item)
        {
            if (this.Root == null)
            {
                this.Root = new BinaryNode<T>(item);
            }
            else
            {
                this.AddItem(item, this.Root);
            }
        }

        private void AddItem(T item, BinaryNode<T> node)
        {
            int compareResults = this.Compare(node.Item, item);

            if (compareResults <= 0)
            {
                if (node.Left == null)
                {
                    node.Left = new BinaryNode<T>(item);
                }
                else
                {
                    this.AddItem(item, node.Left);
                }
            }
            else
            {
                if (node.Right == null)
                {
                    node.Right = new BinaryNode<T>(item);
                }
                else
                {
                    this.AddItem(item, node.Right);
                }
            }
        }

        private int Compare(T x, T y)
        {
            if (this.Comparison != null)
            {
                return this.Comparison(x, y);
            }
            else
            {
                IComparable<T> comparableX = x as IComparable<T>;

                if (comparableX != null)
                {
                    return comparableX.CompareTo(y);
                }
                else
                {
                    IComparable<T> comparableY = y as IComparable<T>;

                    if (comparableY != null)
                    {
                        return comparableY.CompareTo(x);
                    }
                    else
                    {
                        throw new Exception("At least one must not be null and must implement IComparable<T>.");
                    }                    
                }                
            }
        }

        public override string ToString()
        {
            StringBuilder stringBuilder = new StringBuilder();

            foreach (var item in this)
            {
                stringBuilder.Append(item.ToString());
                stringBuilder.Append(" ");
            }

            return stringBuilder.ToString();
        }

        public IEnumerator<T> GetEnumerator()
        {
            if (this.Root != null)
            {
                Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();

                stack.Push(this.Root);

                HashSet<BinaryNode<T>> alreadyStacked = new HashSet<BinaryNode<T>>();

                while (stack.Count != 0)
                {
                    BinaryNode<T> currentNode = stack.Pop();

                    if (currentNode.Left == null &&
                        currentNode.Right == null)
                    {
                        yield return currentNode.Item;
                    }
                    else
                    {
                        if (alreadyStacked.Contains(currentNode))
                        {
                            yield return currentNode.Item;
                        }
                        else
                        {
                            if (currentNode.Left != null)
                            {
                                stack.Push(currentNode.Left);
                            }

                            stack.Push(currentNode);

                            alreadyStacked.Add(currentNode);

                            if (currentNode.Right != null)
                            {
                                stack.Push(currentNode.Right);
                            }
                        }
                    }
                }
            }
        }

        
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        
    }
}
